//#include <iostream>
//#include <vector>
//#include <cstring>
//using namespace std;
//
//const int N = 1e3 + 10;
//int v[N], w[N];
//int n, V;
//
//int main()
//{
//    cin >> n >> V;
//    for (int i = 0; i < n; i++)
//        cin >> v[i] >> w[i];
//    int dp[V + 1];
//    memset(dp, 0, sizeof(int) * (V + 1));
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = V; j >= 1; j--)
//        {
//            if (j >= v[i - 1])
//                dp[j] = max(dp[j], dp[j - v[i - 1]] + w[i - 1]);
//        }
//    }
//    std::cout << dp[V] << std::endl;
//
//    memset(dp, 0, sizeof(int) * (V + 1));
//    for (int i = 1; i <= n; i++)
//        dp[i] = -0x3f3f3f3f;
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = V; j > 0; j--)
//        {
//            if (j > v[i - 1])
//                dp[j] = max(dp[j], dp[j - v[i - 1]] + w[i - 1]);
//        }
//    }
//    std::cout << dp[V] << std::endl;
//    return 0;
//}



#include <iostream>
#include <cstring>
using namespace std;

int n, V;
int v[1010] = { 0 }, w[1010] = { 0 };
int dp[1001] = { 0 };
int main()
{
    cin >> n >> V;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];

    // ques1
    for (int i = 1; i <= n; i++)
        for (int j = v[i]; j <= V; j++)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    cout << dp[V] << endl;

    /// ques2
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= V; i++)
        dp[i] = -1;
    for (int i = 1; i <= n; i++)
        for (int j = v[i]; j <= V; j++)
            if (dp[j - v[i]] != -1)
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    cout << ((dp[V] == -1) ? 0 : dp[V]) << endl;
    return 0;
}